//
//  ViewController.m
//  XX
//
//  Created by 王郑 on 2017/6/28.
//  Copyright © 2017年 王郑. All rights reserved.
//

#import "ViewController.h"

@interface ViewController ()

@end

@implementation ViewController
int a[200]={
    102240,
    33070,
    84990,
    36240,
    62622,
    55488,
    8000,
    53850,
    53850,
    69180,
    71340,
    59220,
    58420,
    65370,
    30056,
    76890,
    9100,
    101040,
    7300,
    11520,
    38840,
    20896,
    20896,
    28352,
    8960,
    34336,
    32832,
    17920,
    41792,
    20896,
    92000,
    18240,
    22530,
    5070,
    21360,
    32820,
    8100,
    31650,
    8960,
};

bool x[200];//标记第i个元素是否已经使用  // 2038.40,77158.40,8310.40,10348.80,
int N=39;//元素个数
int t=419444;//目标和539226.40
int sum;//当前和
int cmp(const void *a,const void *b)
{
    return *(int *)b-*(int *)a;
}
void backtrace(int n)
{
    if(sum>t)//当前和大于t
        return ;
    if(sum==t)//当前和等于t,输出结果
    {
        for(int j=0;j<n;++j)
        {
            if(x[j])
                NSLog(@"%d",a[j]);
        }
        NSLog(@"啦啦啦\n" );
        return;
    }
    if(n==N)//超过n层
//        NSLog(@"结束了");
        return ;
    for(int i=n;i<N;++i)
    {
        if(x[i]==false)//未使用
            
        {
            x[i]=true;
            sum+=a[i];
            backtrace(i+1);
            x[i]=false;
            sum-=a[i];
            while(i<N-1 && a[i]==a[i+1])//跳过相同的
                i++;
        }
    }
}

- (void)viewDidLoad {
    [super viewDidLoad];

        sum=0;
        memset(x,0,sizeof(x));
        qsort(a,N,sizeof(a[0]),cmp);
        backtrace(0);
    

//    NSArray *arr = @[@(83500.00),
//                     @(63200.00),
//                     @(61670.00),
//                     @(46830.00),
//                     @(29798.40),
//                     @(27798.40),
//                     @(27798.40),
//                     @(26010.00),
//                     @(25798.40),
//                     @(25798.40),
//                     @(25200.00),
//                     @(6800.00),
//                     @(1100.00),
//                     @(500.00),
//                     @(452.00),
//                     @(452.00),
//                     @(452.00),
//                     @(339.00),
//                     @(160.00),
//                     @(160.00),
//                     @(160.00),
//                     @(160.00)];
//
//
//    NSInteger sum = 0;
//    for (NSNumber *a in arr) {
//
//        NSInteger tp = [a integerValue];
//        sum+=tp;
//    }
//    NSLog(@"%d",sum);
}


- (void)didReceiveMemoryWarning {
    [super didReceiveMemoryWarning];
    // Dispose of any resources that can be recreated.
}


@end
